


//删除排序数组中的重复项
class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        int dest = 0, cur = 0, n = nums.size();
        while(cur < n)
        {
            if(nums[cur] != nums[dest]) swap(nums[++dest], nums[cur++]);
            else ++cur;
        }
        return dest + 1;
    }
};



//JZ39 数组中出现次数超过一半的数字
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    // int MoreThanHalfNum_Solution(vector<int>& numbers) 
    // {
    //     sort(numbers.begin(),numbers.end());
    //     return numbers[numbers.size()/2];
    // }
    int MoreThanHalfNum_Solution(vector<int>& numbers) 
    {
        sort(numbers.begin(), numbers.end());
        return numbers[numbers.size()/2];
    }

};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;

        int n = nums.size();
        for(int i = 0; i < n; )
        {
            //1. 优化
            if(nums[i] > 0) break;
            int left = i + 1, right = n - 1;
            int target = -nums[i];
            while(left < right)
            {
                int sum = nums[left] + nums[right];                
                if(target > sum)    ++left;
                else if(target < sum)   --right;
                else 
                {
                    ret.push_back({nums[i],nums[left],nums[right]});
                    //2.0 去重left、right
                    while(nums[right] == nums[right - 1] && right > left) --right;
                    while(nums[left] == nums[left + 1] && left < right) ++left;
                    --right, ++left;
                }
            }
            i++;
            //2.1 去重i ,与前一个数进行比较！！！ 
            while(i < n && nums[i] == nums[i-1]) ++i;
        }
        return ret;
    }
};

